package com.kjc.demo.basic.algorithm;

public class InsertSort {
	
	public static int[] insertSort(int[] array){
        for(int i=1;i<array.length;i++)//第0位独自作为有序数列，从第1位开始向后遍历
        {
            if(array[i]<array[i-1])//0~i-1位为有序，若第i位小于i-1位，继续寻位并插入，否则认为0~i位也是有序的，忽略此次循环，相当于continue
            {
                int temp=array[i];//保存第i位的值
                int j = i - 1;
                while(j>=0 && temp<array[j])//从第i-1位向前遍历并移位，直至找到小于第i位值停止
                {
                    array[j+1]=array[j];
                    j--;
                }
                array[j+1]=temp;//插入第i位的值
            }
        } 
        return array;
    }
	
	    public static void insertSortNew(String[] args){
	        int arr[] = { 5 , 2 , 6 , 0 , 9};   
	        System.out.println("排序前的数据：");
	        for (int i = 0; i < arr.length; i++) {            
	            System.out.print(arr[i] + " ");
	        }
	        //直接插入排序
	        for (int i = 1; i < arr.length; i++) {
	            int j = i;
	            //待排序中的元素比已排序的元素小，则交换位置
	            while (j > 0 && arr[j] < arr[j - 1]) {
	                int temp = arr[j];
	                arr[j] = arr[j-1];
	                arr[j-1] = temp;
	                j--;
	            }
	        }     
	        System.out.println();
	        System.out.println("排序后的数据：");
	        for (int i = 0; i < arr.length; i++) {            
	            System.out.print(arr[i] + " ");
	        }                
	    }        

	
	public static void main(String[] args) {
		int[] arr = new int[] {2,3,5,6,8,1,10,9};
		arr = insertSort(arr);
		for(int i : arr) {
			System.out.print(i+" ");
		}
	}
}
